//
// Created by francklinson on 2021/5/7.
//
#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution { // 题解  贪心 模拟
public:
    int leastInterval(vector<char> &tasks, int n) {
        // 统计每个任务需要完成的次数
        unordered_map<char, int> freq;
        for (char ch: tasks) {
            ++freq[ch];
        }

        // 任务总数
        vector<int> nextValid, rest; // 每种任务下一个可行的时间，以及每种任务剩余需要完成的数量
        for (auto x: freq) {
            nextValid.push_back(1); // 初始都是在1时刻可行
            rest.push_back(x.second);
        }

        int time = 0;
        for (int i = 0; i < tasks.size(); ++i) {
            ++time; // 时间增加
            int minNextValid = INT_MAX; // 下一刻可行的时间
            for (int j = 0; j < freq.size(); ++j) { // 遍历任务
                if (rest[j]) {
                    minNextValid = min(minNextValid, nextValid[j]); // 最近的可行的任务
                }
            }
            time = max(time, minNextValid);  // 跳过等待的时间
            int best = -1;
            for (int j = 0; j < freq.size(); ++j) {
                if (rest[j] && nextValid[j] <= time) {
                    if (best == -1 || rest[j] > rest[best]) {
                        best = j; // 同等条件下，安排剩余次数最多的
                    }
                }
            }
            nextValid[best] = time + n + 1; // 被安排的任务的下一个可行时间
            --rest[best];  // 被安排的任务需要完成的次数-1
        }

        return time;
    }
};
class Solution2 { // 题解2   数学推导 看不懂
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char, int> freq;
        for (char ch: tasks) {
            ++freq[ch];
        }

        // 最多的执行次数
        int maxExec = max_element(freq.begin(), freq.end(), [](const auto& u, const auto& v) {
            return u.second < v.second;
        })->second;
        // 具有最多执行次数的任务数量
        int maxCount = accumulate(freq.begin(), freq.end(), 0, [=](int acc, const auto& u) {
            return acc + (u.second == maxExec);
        });

        return max((maxExec - 1) * (n + 1) + maxCount, static_cast<int>(tasks.size()));
    }
};



int main() {
    vector<char> task{'A','A','A','A','A','A','B','C','D','E','F','G'};
    Solution2 sol;
    cout << sol.leastInterval(task, 2) << endl;
    return 0;
}